package tree;

import offer.TreeNode;

/**
 * 根据一棵树的前序遍历与中序遍历构造二叉树。
 *
 * 注意:
 * 你可以假设树中没有重复的元素。
 *
 * 例如，给出
 *
 * 前序遍历 preorder = [3,9,20,15,7]
 * 中序遍历 inorder = [9,3,15,20,7]
 * 返回如下的二叉树：
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 *
 */
public class leetCode105_buildTree {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0)return null;
        return build(preorder,0,preorder.length - 1,
                    inorder,0,inorder.length - 1);
    }


    public TreeNode build(int[] preorder,int preBegin,int preEnd,
                          int[] inorder, int inBegin,int inEnd){

        if(preBegin > preEnd){
            return null;
        }

        TreeNode root = new TreeNode(preorder[preBegin]);
        int inIndex = -1;
        for (int i = inBegin; i <= inEnd; i++) {
            if(root.val == inorder[i]){
                inIndex = i;
                break;
            }
        }

        int leftLength = inIndex - inBegin;

        root.left = build(preorder,preBegin + 1,preBegin + leftLength,
                              inorder,inBegin,inIndex - 1);
        root.right = build(preorder,preBegin + leftLength + 1,preEnd,
                                inorder,inIndex + 1,inEnd);

        return root;




    }


}
